package list;

/**
 * 面试题 02.07. 链表相交
 *
 * @author Api
 * @date 2023/10/11 0:15
 */
public class Code0207_LinkedListIntersection {
    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0;
        int lenB = 0;
        while (curA != null) { // 求链表A的长度
            lenA++;
            curA = curA.next;
        }
        while (curB != null) {
            lenB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            // 1. swap(lenA,lenB)
            int tempLen = lenA;
            lenA = lenB;
            lenB = tempLen;
            // 2. swap(curA, curB)
            ListNode tempNode = curA;
            curA = curB;
            curB = tempNode;
        }
        // 求长度
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上（末尾位置对齐）
        while (gap-- > 0) {
            curA = curA.next;
        }
        // 遍历curA和curB，遇到相同则直接返回
        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}
